package org.java.mode;

import java.util.List;
import java.util.ArrayList;

/**
 * 分解质因数
 */
public class GetFactor {

	public static void main(String[] args) {
		List<Long> factors = getFactors(3527165337242843098L, 2);
		System.out.println(factors);
	}

	/**
	 * 通过递归实现分解质因数
	 * 
	 * @param n
	 *            要分解的数字
	 * @param factor
	 *            起始因子
	 * 
	 * @return 分解结果
	 */
	private static List<Long> getFactors(long n, long factor) {
		// 不断增大 factor 直到能整除 n
		while (n % factor != 0 && factor < n) {
			// 得到 2,3,5,7,9,11,13,...
			factor = factor < 2 ? 2 : factor == 2 ? 3 : factor + 2;
		}

		List<Long> result;
		if (factor >= n) { // 因子已经涨到和 n 一样大，说明 n 本身就是因子。这时递归完成。
			result = new ArrayList<Long>();
		} else { // 因子能够整除 n，于是继续分解除以因子后的结果
			result = getFactors(n / factor, factor); // 向下递归
		}

		result.add(factor);
		return result;
	}
}
